//
//  5.用两个栈实现队列.swift
//  数据结构与算法
//
//  Created by ZERO on 2021/5/17.
//

import Foundation
/*
 题目：用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
 思路：创建两个栈stack1和stack2，使⽤两个“先进后出”的栈实现⼀个“先进先出”的队列。 我们通过⼀个具体的例⼦分析往该队列插⼊和删除元素的过程。⾸先插⼊⼀个元素a，不妨先把它插⼊到stack1，此时stack1中的元素有{a}，stack2为 空。再压⼊两个元素b和c，还是插⼊到stack1中，此时stack1的元素有{a,b,c}，其中c位于栈顶，⽽stack2仍然是空的。 这个时候我们试着从队列中删除⼀个元素。按照先⼊先出的规则，由于a⽐b、c先插⼊队列中，最先删除的元素应该是a。元素a存储在stack1中，但并 不在栈顶，因此不能直接进⾏删除操作。注意stack2我们⼀直没有使⽤过，现在是让stack2发挥作⽤的时候了。如果我们把stack1中的元素逐个弹出压⼊
 stack2，元素在stack2中的顺序正好和原来在stack1中的顺序相反。因此经过3次弹出stack1和要⼊stack2操作之后，stack1为空，⽽stack2中的元素是
 {c,b,a}，这个时候就可以弹出stack2的栈顶a了。此时的stack1为空，⽽stack2的元素为{b,a}，其中b在栈顶。 因此我们的思路是：当stack2中不为空时，在stack2中的栈顶元素是最先进⼊队列的元素，可以弹出。如果stack2为空时，我们把stack1中的元素逐个 出并压⼊stack2。由于先进⼊队列的元素被压倒stack1的栈底，经过弹出和压⼊之后就处于stack2的栈顶，有可以直接弹出。如果有新元素d插⼊，我们直接 把它压⼊stack1即可。
 */
func offer_5() {
    let s = Solution()
    s.push(3)
    s.push(2)
    s.push(1)
    print(s.pop()!)
    print(s.pop()!)
    print(s.pop()!)
}

fileprivate class Solution {
    private var stack1 = Stack<Int>()
    private var stack2 = Stack<Int>()
    
    func push(_ code: Int) {
        stack1.push(element: code)
    }
    
    func pop() -> Int? {
        if stack2.isEmpty() {
            while stack1.count > 0 {
                stack2.push(element: stack1.pop()!)
            }
        }
        return stack2.pop()
    }
}
